This invention relates to the field of telecommunication networks and packet switching and, in particular, to medium access control protocols and transmission scheduling in shared media point to multipoint cell-switched networks.
As the concept of asynchronous transfer mode (ATM) gains wide acceptance, network designers are facing the issue known as xe2x80x9cthe last mile problemxe2x80x9d. There are cost effective ways to switch user information locally, i.e. LAN and voice switches, just as there are cost-effective ways to interconnect cities, i.e. fiber optics cables carrying synchronous digital hierarchy (SDH) traffic, which can serve as trunks for ATM switches. The xe2x80x9clast milexe2x80x9d is the region between the user and the wide area network.
There are two classes of last mile access: dedicated links and shared media. Dedicated links include the copper twisted pairs (possibly with ADSL enhancement), some coax installations and point to point radios. Shared media include point to multipoint radio, coax, and some fiber optics solutions. Shared media has two main advantages: first, cost reduction at the head-end by serving many customers with a single unit; and second, the flexibility of dynamically allocating the shared capacity among the users based on instantaneous needs.
However, shared media poses several issues, such as how to maintain integrity if one user fails and floods the media with interfering signals and how to share the media fairly among the users. In particular, there is an issue of how to guarantee each user a quality of service (QoS) performance for each particular service, such as constant bit rate circuit emulation services (CBR-CES) and available bit rate (ABR).
These issues have been partially addressed by a family of techniques that include the following:
1. A base station (BS) controls the operation of the subscriber terminals (STs).
2. Transmissions on the medium can be made from the BS to STs (downstream) or from ST to the BS (upstream) but not from ST to ST.
3. The downstream transmission is a broadcast to all users, and the destination ST is specified by a media access control (MAC) address.
4. The upstream transmission is moderated by the BS, and the BS specifies which ST will transmit at each given transmission opportunity (or xe2x80x9cslotxe2x80x9d).
5. All user-generated traffic is transmitted based on grants from the BS, and no data is transmitted in a contention slot, such as slotted ALOHA.
6. Contention slots or polling are used for bandwidth reservation.
The various techniques differ in the way they support multiple services in the upstream direction. For example, a customary technique is to define a time division multiplex (TDM) table such that each ST is allocated a few slots within the TDM table based on the user""s traffic load. The TDM table includes contention slots for bandwidth requests and one-user slots for data transfer. However, the customary technique is too slow to respond to momentary bursts of traffic of specific users.
An alternative technique disclosed in application Ser. No. 08/708,593 eliminates the TDM table at the ST and instead maintains the timing information at the BS for all users. In accordance with the alternative technique, the BS calculates the time intervals of CBR virtual circuits (VC) and queues a grant for each VC when its time has matured. Non-time-critical services such as ATM nrt-VBR send requests via contention slots or attached to any upstream cell MAC overhead. The requests carry a summary of the total buffer occupancy in the ST (excluding CBR), and the ST calculates an urgency figure for the buffer""s status. The requests are prioritized by the BS. Once the BS decides which ST gets a grant, the grant is sent without specifying which VC within an ST can use the grant. Thus, the alternative technique provides non-directed grants.
Another example of scheduling ATM flow over a wireless network is discussed in the paper entitled xe2x80x9cGuarantee Quality of Service Wireless Access ATM Networksxe2x80x9d by C-S. Chang, K-C. Chen, M-Y You and J-F. Chang in IEEE J. Sel. Areas Com. Vol. 15. No. 1, January 1997, p. 106. The paper provides performance analysis of a wireless ATM network in which CBR transmission xe2x80x9ctokensxe2x80x9d are generated periodically and have higher priority than non-CBR traffic. Among the CBR tokens, the one selected for current transmission is the one with the highest static priority. This approach allows a bound to be calculated on the worst case delay of each VC. However, this approach lacks fairness, because a VC of similar quality objectives but lower priority will get a lower grade of service.
In accordance with the present invention, requests and grants are directed, i.e. specified per VC. Accordingly, in one embodiment of the present invention, a per-VC scheduler is provided, and MAC layer protocol formats for implementing requests and grants are also provided. A point to multipoint microwave ATM network and other shared media with mechanisms to request and grant bandwidth in the shared media are also disclosed.
In one embodiment, an ATM access network includes subscriber terminals (STs) located in several buildings in a section of a city and a base station located within a few kilometers of the STs. Each ST is connected to a plurality of user interfaces such as an ISDN basic rate interface or a 10BaseT Ethernet. The user traffic is converted to ATM traffic for upstream transmission. ATM traffic is also received from the BS and converted to the user interface format. After an ST has completed an admission process that sets the right carrier frequency, transmission power and transmission delay, the STP is ready to provide ATM services.
ATM traffic flow scheduling in accordance with one embodiment of the present invention includes the following:
1. Requests and grants that include virtual circuit (VC) information, in which a VC represents a virtual path identifier/virtual channel identifier (VPI/VCI) of an ATM cell""s flow.
2. A periodical request-less per VC scheduler residing at the BS, called a xe2x80x9cvirtual framerxe2x80x9d.
3. A request-based per VC scheduler residing at the BS, called a xe2x80x9cvirtual shaperxe2x80x9d.
In one embodiment, if the service of a particular VC is constant bit rate (CBR) or otherwise requires critical real time performance, then a BS scheduler called a xe2x80x9cvirtual framerxe2x80x9d is invoked to provide periodical request-less grants to the VC. Specifically, the grants specify which ST and which VC within the ST can use the grant to transmit one ATM cell, and the grants are transmitted as MAC overhead in the downstream direction.
More specifically, the virtual framer resides at the BS and includes a table of traffic records that define the source ST and the cell transmission interval. A microcontroller writes these records at the connection set up time. The microcontroller also generates a request on behalf of the ST to send one grant. The request is queued in the virtual framer, and the request is then processed. The virtual framer checks a traffic record, calculates the next compliant time (NCT), which for CBR traffic is simply the last calculated transmission time plus the cell""s transmission interval. A grant is generated with the NCT as a priority descriptor. The grant enters a sorted priority queue in which it waits until the grant has xe2x80x9cmaturedxe2x80x9d (i.e., until the current time has met or exceeded the NCT). The matured grant is placed in a high priority queue of matured grants, and the matured grant is sent to the ST via the MAC overhead when it reaches the head of the line. Also, when a grant has matured, a new request is generated for the VC, and the new request is placed in the input queue of the virtual framer to keep the periodical scheduling process active. The traffic record includes the NCT variable which is compared with the current time. Because the time variable grows indefinitely, a finite binary number will overflow and indicate an earlier time than it should. A numerical roll-over technique similar to Gray coding is used so that as long as the cell transmission interval is significantly shorter than the NCT roll-over interval, no timing ambiguity will occur.
Accordingly, the virtual framer provides a scheduling mechanism that is useful for CBR traffic and real time VBR (rt-VBR) traffic. Thus, in one embodiment, rt-VBR traffic is served by the virtual framer using periodic grants, and if the ST VC has no traffic, the ST transmits idle cells.
However, some CBR traffic may include extra cells for operation and management (OAM) which are scheduled in addition to the period. In one embodiment, OAM traffic is served by a request-based mechanism which generates requests that are treated at the BS as high-priority VBR traffic using a VBR scheduling mechanism as described below.
In one embodiment, non-real-time (nrt) traffic is served by a virtual shaper. The nrt traffic is referred to below as xe2x80x9cVBRxe2x80x9d, but the nrt traffic may correspond to any ATM class of service, including available bit rate (ABR), unspecified bit rate (UBR), and VBR. In an alternative embodiment, OAM cells of CBR services and CBR services can use the virtual shaper as an alternative to the virtual framer, thereby trading off delay for link utilization.
In one embodiment, in xe2x80x9cVBRxe2x80x9d mode, an ST generates a request for each VC that has a new cell for transmission. The request may be for multiple cells of the same VC. The ST then places these requests in priority queues, which in a preferred embodiment are static priority FIFO queues. The requests wait for the next opportunity to be transmitted. The opportunity arrives when either an ATM cell from the ST is transmitted, or when a contention minislot is granted and the ST has won the right to transmit based on the contention protocol. If the request arrives without collision at the BS, the request is placed at the input queue of the virtual shaper. If more than one cell is requested, the request is broken into multiple single requests. The request at the head of the queue is processed first. The virtual shaper checks the table entry of the VC and calculates a next compliant time (NCT) based on the recent history of the VC.
However, unlike the CBR case, the traffic parameters may be quite complex, because the traffic parameters describe the rules of flow for the VC. The rules of flow for the VC are equivalent to the traffic shaping parameters used in ATM interfaces to guarantee cell timing compliance. A real shaper would keep a history of the recent cells transmitted and would delay the current cell forwarding until its timing complies. In contrast, the virtual shaper simply calculates the next compliant time (NCT) for the cell and places a grant with the NCT in a priority queue.
At this point, there are two possible approaches. The grant may be placed in a waiting queue until it matures (as described in the CBR case above), or the grant may be sent directly to a sorted priority queue. In the first approach, all grants result in a transmission that complies with the ATM traffic contract. But the first approach is a non-work-conserving scheduling discipline, because requests can be waiting while the upstream channel is idle. In the second approach, the traffic shaping is not preserved in the air interface (but it can be corrected by the traffic shaper), but the air bandwidth is utilized efficiently.
The virtual shaper may include a variety of traffic description parameters. However, a preferred embodiment uses a dual leaky bucket algorithm which is customary with VBR traffic. The ATM Forum has defined a leaky bucket operation by a protocol called xe2x80x9cGeneric Cell Rate Algorithmxe2x80x9d or GCRA(t1,t2), described in UNI 3.1. Thus, in one embodiment, the virtual shaper emulates two leaky buckets, one with GCRA(1/PCR,CDV), PCR representing peak cell rate and CDV representing cell delay variation, and one with GCRA(1/SCR,BT), SCR representing sustained cell rate and BT representing Burst Tolerance. A real shaper maintains leaky bucket parameters (depth of the bucket and last compliant time) for each of the two buckets, the next compliant time for a new cell based on both buckets, and delay the cell until the NCT. In contrast, the virtual bucket similarly calculates the NCT of a request but then queues the request in the maturing or sorted priority queue.
In the work-conserving mode, the NCT value becomes a fairness guarantee parameter. In particular, if multiple VCs request bandwidth in excess of their traffic contract, the VCs will get the requested bandwidth, but the NCT values will interleave grants for VCs with similar traffic parameters and defer grants for VCs with lower speed. For example, if a first VC has an SCR of 10 cells/sec, a second VC has an SCR of 100 cells/sec, and for both BT=0, then the NCT values of the first VC are 0, 0.1, 0.2, . . . , and the NCT values of the second VC are 0, 0.01, 0.02, . . . As a result, when the VCs are sorted by the earliest NCT, each VC will get one grant, and then the second VC will get about nine more grants before the first VC gets an additional grant. Accordingly, the above example illustrates an approximate weighted fair queuing (WFQ) discipline in which excess bandwidth is allocated among users based on the relative speeds allocated to each user. Thus, the virtual shaper provides a fair allocation of excess bandwidth.
In one embodiment, the NCT value can be a limited-size binary word (e.g., 18-bit) to which more bits can be added on the most significant side as a static priority. The static priority value is fixed for a given VC and does not vary when the NCT value is updated. Accordingly, a sorted priority can be grouped into static priority subclasses. Also, OAM cells of CBR traffic may be allocated the lowest static priority value (i.e. the highest priority) and thus served first.
Because VBR traffic can have long periods of non-activity, the time overflow mechanism mentioned above is insufficient. Accordingly, a refresh mechanism is provided in which all VBR traffic records are scanned periodically, and a time mark is stamped by setting a first bit. If in a second visit the first bit has not been cleared, then a second bit is set. For every request, the scheduler checks the first and second bits in the VC traffic record. If the first and second bits are both set, then the NCT is set to the current time, and the leaky buckets are cleared. The first and second bits are cleared for each request of the VC.